package test.list;

// key-value 模型
public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;


        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }


    private Node[] array;
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 8;//默认桶的大小

    public static void test(){
        HashBucket hashBucket = new HashBucket();
        //增
        System.out.println("增加后：{99：100；9：10；8：9；80：81}");
        System.out.println("此时数组长度为3");
        System.out.println(hashBucket.put(99,100));
        System.out.println(hashBucket.put(9,10));
        System.out.println(hashBucket.put(8,9));
        System.out.println("该操作后数组长度为7");
        System.out.println(hashBucket.put(80,81));

        //查
        System.out.println("查键为9的值");
        System.out.println(hashBucket.get(9));
    }
    public static void main(String[] args){
        test();
    }

    //增
    public int put(int key, int value) {
        if(loadFactor() >= LOAD_FACTOR){
            resize();
        }
        Node node = new Node(key,value);
        //计算下标
        int index = hashCode(key);
        //如果该下标没有元素
        if(array[index] == null){
            array[index] = node;
        }else{
            //如果该下标有元素
            Node cur = array[index];
            int bucketSize = 0;
            while(cur.next != null){
                bucketSize++;
                cur = cur.next;
                if(bucketSize >= DEFAULT_SIZE){
                    resize();
                    put(key, value);
                }
            }
            cur.next = node;
        }
        size++;
        return index;
    }

    private int hashCode(int key) {
        return key % array.length;
    }

    //扩容
    private void resize() {
        // 创建一个更大的数组，数组长度为素数
        int length = array.length * 2;
        //判断是否找到素数
        boolean flag = true;
        //枚举找素数
        for(int num = length;num < array.length * 3;num++){
            flag = true;
            for(int n = 2;n < num;n++){
                if(num % n == 0){
                    //该数不是素数
                    flag = false;
                    break;
                }
            }
            if(flag){
                //找到了
                length = num;
                break;
            }
        }
        Node[] newArray = new Node[length];
        //新数组替代旧数组
        for(Node cur:array){
            for(;cur != null;cur = cur.next){
                int index = cur.key % newArray.length;
                Node newCur = newArray[index];
                if(newCur == null){
                    //新数组 该下标链表 为空
                    newArray[index] = new Node(cur.key,cur.value);
                }else{
                    //该下标链表 不为空
                    //遍历链表直到 该下标链表 的尾巴
                    while(newCur.next != null){
                        newCur = newCur.next;
                    }
                    newCur.next = new Node(cur.key,cur.value);
                }
            }
        }
        array = newArray;
    }

    //计算是否需要扩容的关键值
    private double loadFactor() {
        return size * 1.0 / array.length;
    }

    //创建哈希桶
    public HashBucket() {
        array = new Node[3];
        size = 0;
    }

    //查（根据键获取值）
    public int get(int key) {
        int index = hashCode(key);
        Node cur = array[index];
        if(cur.key == key){
            return cur.value;
        }else{
            while(cur != null){
                if(cur.key == key){
                    return cur.value;
                }
                cur = cur.next;
            }
        }
        return -1;
    }
}
